// Go作者版权所有。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

package ssa

import (
	"cmd/compile/internal/types"
	"fmt"
)

// edgeMem记录一个后缘和内存
// phi函数位于必须
// 当重新安排检查替换后缘时，将更新。
type edgeMem struct {
	e Edge
	m *Value // e目的地内存的phi
}

// 重写目标是一个值argindex对，表示
// 应用重写的位置。请注意，这是针对值，
// 不适用于块控件，因为块控件不是目标
// 用于插入重新计划检查时执行的重写。
type rewriteTarget struct {
	v *Value
	i int
}

type rewrite struct {
	before, after *Value          // before是重写前的预期值，after是安装的新值。
	rewrites      []rewriteTarget // 这次重写的所有目标。
}

func (r *rewrite) String() string {
	s := "\n\tbefore=" + r.before.String() + ", after=" + r.after.String()
	for _, rw := range r.rewrites {
		s += ", (i=" + fmt.Sprint(rw.i) + ", v=" + rw.v.LongString() + ")"
	}
	s += "\n"
	return s
}

// insertLoopReschedChecks在循环后缘上插入重新安排检查。
func insertLoopReschedChecks(f *Func) {
	// TODO:在导出数据中记录拆分信息时，仅在拆分无呼叫路径上可以到达的后缘上插入检查。

	// 循环重新调度检查将堆栈指针与
	// per-g堆栈已绑定。如果指针无效，
	// 这意味着需要重新安排检查。
	// None
	// 步骤：
	// 1.定位后缘。
	// 2.在块末尾记录内存定义，以便
	// 可以适当修改mem的SSA图。
	// 3.确保mem所需的phi功能
	// 在图中显示，最初带有琐碎的输入。
	// 4.记录所有要修改的mem用途；
	// 应用修改（分为两个步骤以简化和
	// 避免了繁琐的顺序依赖关系）。
	// 5.重写后缘，包括重新安排检查，
	// 并使用新的
	// mem的定义。

	if f.NoSplit { // nosplit函数不会重新调度。
		return
	}

	backedges := backedges(f)
	if len(backedges) == 0 { // 没有后缘意味着没有重新安排检查。
		return
	}

	lastMems := findLastMems(f)

	idom := f.Idom()
	po := f.postorder()
	// 支配树中的排序问题；重要的是
	// 支配树的行走也是一个前序（即，一个节点是
	// 仅在访问了其所有非后缘前辈后访问）。
	sdom := newSparseOrderedTree(f, idom, po)

	if f.pass.debug > 1 {
		fmt.Printf("before %s = %s\n", f.Name, sdom.treestructure(f.Entry))
	}

	tofixBackedges := []edgeMem{}

	for _, e := range backedges { // TODO:如果在导出数据中记录了声明和推断的nosplit，则可以通过循环中的调用在此处进行筛选。
		tofixBackedges = append(tofixBackedges, edgeMem{e, nil})
	}

	// 可能没有内存状态（没有全局/指针加载/存储或调用）
	if lastMems[f.Entry.ID] == nil {
		lastMems[f.Entry.ID] = f.Entry.NewValue0(f.Entry.Pos, OpInitMem, types.TypeMem)
	}

	memDefsAtBlockEnds := make([]*Value, f.NumBlocks()) // 对于每个块，在其底部可以看到mem def。可能是之前街区的。

	// 通过后续块向前传播最后一个mem定义。
	for i := len(po) - 1; i >= 0; i-- {
		b := po[i]
		mem := lastMems[b.ID]
		for j := 0; mem == nil; j++ { // 如果没有def，那么就没有phi，因此可见的mem在所有前辈中都是相同的。
			// 循环，因为可能有尚未访问的后缘。
			mem = memDefsAtBlockEnds[b.Preds[j].b.ID]
		}
		memDefsAtBlockEnds[b.ID] = mem
		if f.pass.debug > 2 {
			fmt.Printf("memDefsAtBlockEnds[%s] = %s\n", b, mem)
		}
	}

	// 从块映射到块中新插入的φ函数。
	newmemphis := make(map[*Block]rewrite)

	// 根据需要插入phi函数，以便将来更改流图。
	for i, emc := range tofixBackedges {
		e := emc.e
		h := e.b

		// 在“h”处查找存储器输入的phi函数（如果有）。
		var headerMemPhi *Value // 查找标题mem phi

		for _, v := range h.Values {
			if v.Op == OpPhi && v.Type.IsMemory() {
				headerMemPhi = v
			}
		}

		if headerMemPhi == nil {
			// 如果标题为nil，则从控制符生成一个微不足道的phi
			mem0 := memDefsAtBlockEnds[idom[h.ID].ID]
			headerMemPhi = newPhiFor(h, mem0)
			newmemphis[h] = rewrite{before: mem0, after: headerMemPhi}
			addDFphis(mem0, h, h, f, memDefsAtBlockEnds, newmemphis, sdom)

		}
		tofixBackedges[i].m = headerMemPhi

	}
	if f.pass.debug > 0 {
		for b, r := range newmemphis {
			fmt.Printf("before b=%s, rewrite=%s\n", b, r.String())
		}
	}

	// dfPhiTargets注意到，在占主导地位的前沿领域，对潜在危险装置的投入不应
	// 被重写为某些外部重写的支配子代的一部分。
	dfPhiTargets := make(map[rewriteTarget]bool)

	rewriteNewPhis(f.Entry, f.Entry, f, memDefsAtBlockEnds, newmemphis, dfPhiTargets, sdom)

	if f.pass.debug > 0 {
		for b, r := range newmemphis {
			fmt.Printf("after b=%s, rewrite=%s\n", b, r.String())
		}
	}

	// 应用收集的重写。
	for _, r := range newmemphis {
		for _, rw := range r.rewrites {
			rw.v.SetArg(rw.i, r.after)
		}
	}

	// 重写后缘以包括重新安排的检查。
	for _, emc := range tofixBackedges {
		e := emc.e
		headerMemPhi := emc.m
		h := e.b
		i := e.i
		p := h.Preds[i]
		bb := p.b
		mem0 := headerMemPhi.Args[i]
		// BBE->p h，
		// 因为我们要插入一个罕见的呼叫，请确保
		// 循环边看起来仍然有可能。
		likely := BranchLikely
		if p.i != 0 {
			likely = BranchUnlikely
		}
		if bb.Kind != BlockPlain { // 后缘可以是无条件的。e、 例如，如果x{something；continue}
			bb.Likely = likely
		}

		// 重写边缘以包括重新安排检查
		// 现有边缘：
		// None
		// bb.Succs[p.i]==边{h，i}
		// h、 Preds[i]==p==边{bb，p.i}
		// None
		// 新大厦:
		// 测试：
		// 如果sp<g.limit{goto sched}
		// 加入
		// 附表：
		// mem1:=呼叫重新设置（mem0）
		// 加入
		// 加入：
		// mem2:=phi（mem0，mem1）
		// 转到h
		// None
		// 并更正HeaderMinphi和HeaderCrphi的arg i
		// None
		// 除此之外：仅包含phi函数的联接块不正确
		// 对于寄存器分配器。因此，没有必要
		// 连接，而以连接为目标的分支必须改为以连接为目标
		// 标头和标头中的其他phi函数是
		// 针对附加输入进行了调整。

		test := f.NewBlock(BlockIf)
		sched := f.NewBlock(BlockPlain)

		test.Pos = bb.Pos
		sched.Pos = bb.Pos

		// 如果sp<g.limit{goto sched}
		// 转投头

		cfgtypes := &f.Config.Types
		pt := cfgtypes.Uintptr
		g := test.NewValue1(bb.Pos, OpGetG, pt, mem0)
		sp := test.NewValue0(bb.Pos, OpSP, pt)
		cmpOp := OpLess64U
		if pt.Size() == 4 {
			cmpOp = OpLess32U
		}
		limaddr := test.NewValue1I(bb.Pos, OpOffPtr, pt, 2*pt.Size(), g)
		lim := test.NewValue2(bb.Pos, OpLoad, pt, limaddr, mem0)
		cmp := test.NewValue2(bb.Pos, cmpOp, cfgtypes.Bool, sp, lim)
		test.SetControl(cmp)

		// 如果为true，则转到sched
		test.AddEdgeTo(sched)

		// 如果为false，则将边重写为标头。
		// 不要删除+添加，因为这会干扰所有其他phi函数
		// 也会弄乱头部的其他边缘。
		test.Succs = append(test.Succs, Edge{h, i})
		h.Preds[i] = Edge{test, 1}
		headerMemPhi.SetArg(i, mem0)

		test.Likely = BranchUnlikely

		// 附表：
		// mem1:=呼叫重新设置（mem0）
		// 转投头
		resched := f.fe.Syslook("goschedguarded")
		// TODO（注册参数）--需要更多详细信息
		mem1 := sched.NewValue1A(bb.Pos, OpStaticCall, types.TypeMem, StaticAuxCall(resched, nil), mem0)
		sched.AddEdgeTo(h)
		headerMemPhi.AddArg(mem1)

		bb.Succs[p.i] = Edge{test, 0}
		test.Preds = append(test.Preds, Edge{bb, p.i})

		// 必须为新的传入边缘更正标头中的所有其他phi函数。
		// 除了孟菲斯，它的值将与原版相同
		// 索引i处的后缘。
		for _, v := range h.Values {
			if v.Op == OpPhi && v != headerMemPhi {
				v.AddArg(v.Args[i])
			}
		}
	}

	f.invalidateCFG()

	if f.pass.debug > 1 {
		sdom = newSparseTree(f, f.Idom())
		fmt.Printf("after %s = %s\n", f.Name, sdom.treestructure(f.Entry))
	}
}

// newPhiFor在b中插入一个新的Phi函数，
// 将所有输入设置为v。
func newPhiFor(b *Block, v *Value) *Value {
	phiV := b.NewValue0(b.Pos, OpPhi, v.Type)

	for range b.Preds {
		phiV.AddArg(v)
	}
	return phiV
}

// rewriteNewPhis更新newphis[h]以记录插入新phi函数的所有位置
// 在块h中，将替换先前的定义。块b是当前正在处理的块；
// 如果b有自己的phi定义，那么它将取代h。
// Defsfoures提供了有关当前变量的其他定义的信息
// （如果为nil，则表示变量不再有效）
// sdom必须产生流图的一个前序，如果递归地遍历，则根到子级。
// 具有dfs postorder提供的订单的newSparseOrderedTree的结果满足以下条件
// 要求
func rewriteNewPhis(h, b *Block, f *Func, defsForUses []*Value, newphis map[*Block]rewrite, dfPhiTargets map[rewriteTarget]bool, sdom SparseTree) {
	// 如果b是一个具有新phi的块，则在支配树中，在其下方应用新的重写。
	if _, ok := newphis[b]; ok {
		h = b
	}
	change := newphis[h]
	x := change.before
	y := change.after

	// 将重写应用于此块
	if x != nil { // 不要把时间浪费在没有定义的常见情况上。
		p := &change.rewrites
		for _, v := range b.Values {
			if v == y { // 不要重写self——phi输入在下面处理。
				continue
			}
			for i, w := range v.Args {
				if w != x {
					continue
				}
				tgt := rewriteTarget{v, i}

				// 控制流可能会重写这个。
				// 按预定顺序访问（sdom如何构建的属性）
				// 确保以正确的顺序查看这些内容。
				if dfPhiTargets[tgt] {
					continue
				}
				*p = append(*p, tgt)
				if f.pass.debug > 1 {
					fmt.Printf("added block target for h=%v, b=%v, x=%v, y=%v, tgt.v=%s, tgt.i=%d\n",
						h, b, x, y, v, i)
				}
			}
		}

		// 重写在后续操作中达到的PHI的适当输入
		// 在支配前沿，自我，和被支配。
		// 如果在b中使用的变量def本身在b中定义，则新的phi函数
		// 没有达到b的继任者。（这假设了一点关于
		// phi使用def-graph，但对于内存来说是正确的。）
		if dfu := defsForUses[b.ID]; dfu != nil && dfu.Block != b {
			for _, e := range b.Succs {
				s := e.b

				for _, v := range s.Values {
					if v.Op == OpPhi && v.Args[e.i] == x {
						tgt := rewriteTarget{v, e.i}
						*p = append(*p, tgt)
						dfPhiTargets[tgt] = true
						if f.pass.debug > 1 {
							fmt.Printf("added phi target for h=%v, b=%v, s=%v, x=%v, y=%v, tgt.v=%s, tgt.i=%d\n",
								h, b, s, x, y, v.LongString(), e.i)
						}
						break
					}
				}
			}
		}
		newphis[h] = change
	}

	for c := sdom[b.ID].child; c != nil; c = sdom[c.ID].sibling {
		rewriteNewPhis(h, c, f, defsForUses, newphis, dfPhiTargets, sdom) // TODO:从递归转换为显式堆栈。
	}
}

// addDFphis创建正确反映（SSA内）所需的新的普通Phi
// 在h处插入变量“x”的新定义（通常但不一定是phi）。
// 这些新的潜在危险源只能发生在h的优势前沿；s区处于优势地位
// h的边界，如果h不严格支配s，并且s是b区的继承者，其中
// b=h或h严格控制b。
// 这些新创建的潜在危险装置本身是新定义，可能需要添加其
// 在自己的优势边界上拥有平凡的phi函数，这是递归处理的。
func addDFphis(x *Value, h, b *Block, f *Func, defForUses []*Value, newphis map[*Block]rewrite, sdom SparseTree) {
	oldv := defForUses[b.ID]
	if oldv != x { // 或者用一个新的定义来代替x，或者如果证明b没有可达到的用途，则用nil来代替
		return
	}
	idom := f.Idom()
outer:
	for _, e := range b.Succs {
		s := e.b
		// 检查优势边界中的phi函数
		if sdom.isAncestor(h, s) {
			continue // h占优势，是b的继承者，因此s不在前沿。
		}
		if _, ok := newphis[s]; ok {
			continue // b的后继s已经有了一个新的phi函数，因此不需要再添加一个。
		}
		if x != nil {
			for _, v := range s.Values {
				if v.Op == OpPhi && v.Args[e.i] == x {
					continue outer // b的后继s有一个旧的phi函数，因此不需要添加另一个。
				}
			}
		}

		old := defForUses[idom[s.ID].ID] // 新的phi功能是正确的，但冗余，将所有输入上的“旧”值组合在一起。
		headerPhi := newPhiFor(s, old)
		// 新的phi将取代s区块和s主导的所有区块中的“旧”phi。
		newphis[s] = rewrite{before: old, after: headerPhi} // 记录新的phi，将标记为“旧”的输入改写为“headerPhi”
		addDFphis(old, s, s, f, defForUses, newphis, sdom)  // 新定义还可能创建新的phi函数。
	}
	for c := sdom[b.ID].child; c != nil; c = sdom[c.ID].sibling {
		addDFphis(x, h, c, f, defForUses, newphis, sdom) // TODO:从递归转换为显式堆栈。
	}
}

// findLastMems将块ID映射到块中的最后一个内存输出op（如果有）
func findLastMems(f *Func) []*Value {

	var stores []*Value
	lastMems := make([]*Value, f.NumBlocks())
	storeUse := f.newSparseSet(f.NumValues())
	defer f.retSparseSet(storeUse)
	for _, b := range f.Blocks {
		// 找到这个街区的所有商店。将其用途分类：
		// storeUse包含由后续存储使用的存储。
		storeUse.clear()
		stores = stores[:0]
		var memPhi *Value
		for _, v := range b.Values {
			if v.Op == OpPhi {
				if v.Type.IsMemory() {
					memPhi = v
				}
				continue
			}
			if v.Type.IsMemory() {
				stores = append(stores, v)
				for _, a := range v.Args {
					if a.Block == b && a.Type.IsMemory() {
						storeUse.add(a.ID)
					}
				}
			}
		}
		if len(stores) == 0 {
			lastMems[b.ID] = memPhi
			continue
		}

		// 找到街区的最后一家商店
		var last *Value
		for _, v := range stores {
			if storeUse.contains(v.ID) {
				continue
			}
			if last != nil {
				b.Fatalf("two final stores - simultaneous live stores %s %s", last, v)
			}
			last = v
		}
		if last == nil {
			b.Fatalf("no last store found - cycle?")
		}
		lastMems[b.ID] = last
	}
	return lastMems
}

// 标记值
type markKind uint8

const (
	notFound    markKind = iota // 块还没有被发现
	notExplored                 // 已发现并在队列中，路由尚未处理
	explored                    // 已发现并在队列中，已处理路由
	done                        // 全部完成，按输出顺序
)

type backedgesState struct {
	b *Block
	i int
}

// backedges返回返回的后续边的切片
// 边缘。对于可约循环，edge.b是页眉。
func backedges(f *Func) []Edge {
	edges := []Edge{}
	mark := make([]markKind, f.NumBlocks())
	stack := []backedgesState{}

	mark[f.Entry.ID] = notExplored
	stack = append(stack, backedgesState{f.Entry, 0})

	for len(stack) > 0 {
		l := len(stack)
		x := stack[l-1]
		if x.i < len(x.b.Succs) {
			e := x.b.Succs[x.i]
			stack[l-1].i++
			s := e.b
			if mark[s.ID] == notFound {
				mark[s.ID] = notExplored
				stack = append(stack, backedgesState{s, 0})
			} else if mark[s.ID] == notExplored {
				edges = append(edges, e)
			}
		} else {
			mark[x.b.ID] = done
			stack = stack[0 : l-1]
		}
	}
	return edges
}
